//46 求数组排列
/*
给定一个无重复数字的整数数组，求其所有的排列方式。

输入是一个一维整数数组，输出是一个二维数组，表示输入数组的所有排列方式

Input: [1,2,3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
*/
// 主函数
vector<vector<int>> permute(vector<int> &nums)
{
	vector<vector<int>> ans;
	backtracking(nums, 0, ans);
	return ans;
}
// 辅函数
void backtracking(vector<int> &nums, int level, vector<vector<int>> &ans)
{
	//
	if (level == nums.size() - 1)
	{
		ans.push_back(nums);
		return;
	}
	for (int i = level; i < nums.size(); i++)
	{
		swap(nums[i], nums[level]);			// 修改当前节点状态
		backtracking(nums, level + 1, ans); // 递归子节点，
		swap(nums[i], nums[level]);			// 回改当前节点状态
	}
}